Given a sequence of n elements from a totally ordered set, and a position in the sequence, the nearest larger neighbor (NLN) query\udreturns the position of the element which is closest to the query position, and is larger than the element at the query position.\udThe problem of finding all nearest larger neighbors has attracted interest due to its applications for parenthesis matching and in\udcomputational geometry [1, 2, 3]. We consider a data structure version of this problem, which is to preprocess a given sequence of\udelements to construct a data structure that can answer NLN queries efficiently. We consider time-space tradeoffs for the problem\udin both the encoding (where the input is not accessible after the data structure has been created) and indexing model, and consider\udcases when the input is in a one dimensional array, and also initiate the study of this problem on two-dimensional arrays.
展开▼
